UVA1189 题解

题目链接

给定一个正整数 nn,求它的一个倍数 mm 使得 mm 只含有数字 0011

我们可以 11 开始进行 dfs\operatorname{dfs},设当前搜索到的数为 kk,则下一次从 10k10k10k+110k+1 进行搜索,搜到 nn 的倍数直接退出。

题目说 mm 不超过 100100 位,为了避免写高精度,我们可以把当前搜索到的数模 nn 的余数传入 dfs\operatorname{dfs},而把搜索到的数作为字符串,每次在末尾添上 0/10/1,同时记录数字的位数,位数到达 100100 停止搜索。

为了加快效率,我们可以加一个剪枝,搜索到一个可行解后停止搜索。

实测效率还是比较快的,代码也很简短,应该很容易理解。

Code

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int n, flag;

void dfs(string s, int cnt, int mod) {
    if (cnt >= 100 || flag) return;
    if (mod == 0) {
        flag = 1;
        cout << s << endl;
        return;
    }
    dfs(s + '0', cnt + 1, mod * 10 % n);
    dfs(s + '1', cnt + 1, (mod * 10 + 1) % n);
}

int main() {
    while (~scanf("%d", &n) && n) {
        flag = 0;
        dfs("1", 1, 1);
    }
    return 0;
}
赞赏